#include "main/utils.h"
using namespace std;

struct PrefixNode {
  PrefixNode* childern[2];
};

void insert(PrefixNode* root, const int& num) {
  auto node = root;
  for (int i = 31; i >= 0; --i) {
    int bit = (num >> i) & 1;
    if (node->childern[bit] == nullptr) {
      node->childern[bit] = new PrefixNode();
    }
    node = node->childern[bit];
  }
}

PrefixNode* buildPrefixTree(const vector<int>& vec) {
  PrefixNode* root = new PrefixNode();
  for (auto num : vec) {
    insert(root, num);
  }
  return root;
}

int maxXOR(const vector<int> vec) {
  PrefixNode* root = buildPrefixTree(vec);
  int max_xor = 0;
  for (auto num : vec) {
    auto node = root;
    int cur_xor = 0;
    for (int i = 31; i >= 0; --i) {
      int bit = (num >> i) & 1;
      if (node->childern[1 - bit]) {
        cur_xor = (cur_xor << 1) + 1;
        node = node->childern[1 - bit];
      } else {
        cur_xor = (cur_xor << 1);
        node = node->childern[bit];
      }
    }
    if (cur_xor > max_xor) {
      max_xor = cur_xor;
    }
  }
  return max_xor;
}

int main() {
  vector<int> vec = {1, 3, 4, 7};
  cout << maxXOR(vec) << endl;

  return 0;
}
